// 给定一个未排序的整数数组nums和一个整数k，返回数组中第k个最大的元素

// 思路，堆排序和快速排序每次排序后都可以确定一个元素的准确排名
// 思路1，利用对堆排序，
// 1. 将无序序列构造成大顶堆，最大值位于序列的首位
// 2. 交换首尾元素，将除了尾部元素的其余元素调整为新的大顶堆，从而确定第二个最大值元素
// 3. 直到获取第k个最大值元素

function findKthLargest(nums, k) {
    buildMaxHeap(nums)
    for (let i = 0; i < k - 1; i++) {
        [nums[0], nums[nums.length - i - 1]] = [nums[nums.length - i - 1], nums[0]]
        heapify(nums, 0, nums.length - i - 2)
    }
    return nums[0]
}

function buildMaxHeap(nums) {
    for (let i = Math.floor(nums.length / 2); i >= 0; i--) {
        heapify(nums, i, nums.length - 1)
    }
}

function heapify(nums, start, end) {
    let left = 2 * start + 1
    let right = left + 1
    while (left <= end) {
        let maxIndex = start
        if (nums[left] > nums[maxIndex]) {
            maxIndex = left
        }
        if (right <= end && nums[right] > nums[maxIndex]) {
            maxIndex = right
        }
        if (maxIndex === start) {
            break
        }
        [nums[start], nums[maxIndex]] = [nums[maxIndex], nums[start]];
        start = maxIndex
        left = 2 * start + 1
        right = left + 1
    }
}

let arr = [3, 2, 1, 5, 6, 4]
let k = 2
console.log(findKthLargest(arr, k));

// 思路2，快速排序每次调整结束都会确定一个元素的最终位置，以该位置划分左右两个子数组，左边子数组都比该元素小，右边子数组都比该元素大
// 只要某次划分恰好是第k个下标就找到了答案

function findKthLargest2(nums, k) {
    return quickSort(nums, 0, nums.length - 1, k)
}

function quickSort(arr, low, high, k) {
    if (low < high) {
        let index = partition(arr, low, high)
        if (index === arr.length - k) {
            return arr[index]
        } else if (index > arr.length - k) {
            // 对左子序列进行递归快速排序
            quickSort(arr, low, index - 1, k)
        } else {
            // 对右子序列进行递归快速排序
            quickSort(arr, index + 1, high, k)
        }
    }
    return arr[arr.length - k]
}

function partition(arr, low, high) {
    let pivot = Math.floor(Math.random() * (high - low)) + low;
    let pivotVal = arr[pivot];
    [arr[low], arr[pivot]] = [arr[pivot], arr[low]];
    let i = low + 1
    for (let j = i; j <= high; j++) {
        if (arr[j] < pivotVal) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++
        }
    }
    [arr[low], arr[i - 1]] = [arr[i - 1], arr[low]];
    return i - 1
}

let arr1 = [3, 2, 1, 5, 6, 4]
let k1 = 2
console.log(findKthLargest2(arr1, k1));